package leetcode.top100;

/**
 * 最长回文子串:使用Manacher算法
 * 应用{@link baseclass.l_String.Code08_ManacherAppPalindRome}
 * 应用{@link Code647_回文子串个数2}
 *
 * @date 2020/3/23 17:17
 */
public class Code05_LongestPalindrome2 {

    public static String longestPalindrome3(String s) {
        if (s == null || s.length() == 0) return s;
        s = getModify(s);
        int rightR = -1;
        int rightCenter = -1;
        int max = 0;
        int maxCenter = -1;
        int[] pCenter = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (i < rightR) {
                //情况2的case1，case2，和case3部分
                pCenter[i] = Math.min(pCenter[2 * rightCenter - i], rightR - i + 1);
            } else {
                pCenter[i] = 1;
            }
            //判断是否能扩。
            while (i - pCenter[i] >= 0 && i + pCenter[i] < s.length()) {
                //情况2的case1和case2必定不会进入
                if (s.charAt(i - pCenter[i]) == s.charAt(i + pCenter[i])) {
                    pCenter[i]++;
                } else {
                    break;
                }
            }
            //更新半径
            if (i + pCenter[i] - 1 > rightR) {
                rightR = i + pCenter[i] - 1;
                rightCenter = i;
            }
            //最大值
            if (pCenter[i] > max) {
                max = pCenter[i];
                maxCenter = i;
            }

        }
        //当前中心maxCenter,回文个数是max-1.
        return s.substring(maxCenter - (max - 1), maxCenter + (max - 1) + 1)
                .replace("#", "");


    }

    private static String getModify(String s) {
        StringBuffer sb = new StringBuffer("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        System.out.println(longestPalindrome3("babad"));
    }
}
